package com.javabase.y2022.m05.day0517.v1;

/**
 * @descriptions: Solution
 * @author: Tom
 * @date: 2022/5/17 上午 09:07
 * @version: 1.0
 */
public class Solution {
    public static void main(String[] args) {
        int[] arr = new int[]{1,4,3,2,56,7,89,12,100};
        new Solution().mergeSorted(arr);
        for (int i = 0; i < arr.length; i++) {
            System.out.print(" " + arr[i]);
        }
    }
    // 歸并排序
    public void mergeSorted(int[] arr) {
        int L = 0;
        int R = arr.length - 1;
        process(arr, 0, R);
    }

    public void process(int[] arr, int L, int R) {
        // base case很重要
        if(L==R){
            return;
        }
        int M = L + ((R - L) >> 1);
        process(arr, L, M);
        process(arr, M + 1, R);
        merge(arr, L, M, R);
    }

    public void merge(int[] arr, int L, int M, int R) {
        int[] help = new int[R - L + 1];
        int p1 = L, p2 = M+1;
        int i = 0;
        while(p1<=M && p2 <=R){
            help[i++] = arr[p1] < arr[p2] ? arr[p1++]:arr[p2++];
        }
        while(p1<=M){
            help[i++] = arr[p1++];
        }
        while(p2<=R){
            help[i++] = arr[p2++];
        }
        for (int j = 0; j < help.length; j++) {
            arr[L+j] = help[j];
        }
    }
}
